package com.zjsru.plan2023.oneday.oneDay202303;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: CookLee
 * @Date: 2023/4/2 多边形三角剖分的最低得分
 * <p>
 * 你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。
 * <p>
 * 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
 * <p>
 * 输入：values = [1,2,3] 输出：6 解释：多边形已经三角化，唯一三角形的分数为 6。
 * <p>
 * 输入：values = [3,7,4,5] 输出：144 解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
 * <p>
 * 输入：values = [1,3,1,4,1,5] 输出：13 解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
 */
public class MinScoreTriangulation {
    
    /**
     * 记忆化搜索
     *
     * @param values 值
     * @return int
     */
    private int n = 0;
    
    int[] values;
    
    private final Map<Integer, Integer> memo = new HashMap<>();
    
    public int minScoreTriangulation(int[] values) {
        this.n = values.length;
        this.values = values;
        return this.dp(0, n - 1);
    }
    
    private int dp(int i, int j) {
        //此时不能构成三角形
        if (i + 2 > j) {
            return 0;
        }
        //此时刚好是一个三角形
        if (i + 2 == j) {
            return this.values[i] * this.values[i + 1] * this.values[j];
        }
        //用数组下标作为Key
        int key = i * this.n + j;
        //检查map中是否存在
        if (!this.memo.containsKey(key)) {
            int minScore = Integer.MAX_VALUE;
            for (int k = i + 1; k < j; k++) {
                //minScore 即是图形面积的总和，分为了三部分：顶点 i,i+1,…,k−1,k, 构成的凸 k−i+1 边形。当 k=i+1 时，这部分不存在。
                //顶点 i,k,j构成的三角形。
                //顶点 k,k+1,…,j−1,j 构成的凸 j−k+1 边形。当 j=k+1时，这部分不存在
                minScore = Math.min(minScore, this.values[i] * this.values[k] * this.values[j] + this.dp(i, k) +
                        this.dp(k, j));
            }
            memo.put(key, minScore);
        }
        return memo.get(key);
    }
    
    public static void main(String[] args) {
        MinScoreTriangulation minScoreTriangulation = new MinScoreTriangulation();
        int[] values = new int[] {1, 3, 1, 4, 1, 5};
        System.out.println(minScoreTriangulation.minScoreTriangulation(values));
    }
}
